package pers.whj.sort;

public class ShellSort<T> extends Sort<T> {
    public ShellSort(T[] data) throws SortException {
        super(data);
    }

    public ShellSort(T[] data, Compare<T> compare) throws SortException {
        super(data, compare);
    }

    @Override
    public void sort(int left, int right) throws SortException {
        sort(mData, mCompare, left, right);
    }

    public static <E> void sort(E[] data) throws SortException {
        sort(data, null);
    }

    public static <E> void sort(E[] data, Compare<E> compare) throws SortException {
        sort(data, compare, 0, data == null ? 0 : data.length - 1);
    }

    public static <E> void sort(E[] data, Compare<E> compare, int left, int right) throws SortException {
        check(data, compare, left, right);
        if (right - left >= 1) {
            int i, j, gap = right - left + 1;
            do {
                gap = gap / 3 + 1;
                for (i = left + gap; i <= right; i++) {
                    if (compare.swap(data[i - gap], data[i])) {
                        E temp = data[i];
                        j = i - gap;
                        do {
                            data[j + gap] = data[j];
                            j -= gap;
                        } while (j >= left && compare.swap(data[j], temp));
                        data[j + gap] = temp;
                    }
                }
            } while (gap > 1);
        }
    }
}